Copyright ã1995 by NeXT Computer, Inc.  All Rights Reserved.

IXBTreeCursor

Inherits From:	Object

Conforms To:	IXCursorPositioning

Declared In:	btree/IXBTreeCursor.h

Class Description

An IXBTreeCursor provides access to the keys and values stored in an IXBTree.  It's essentially a pointer into the IXBTree's key space, and may be positioned by key to perform operations on the value stored at a given location.  See the IXCursorPositioning protocol specification for information on cursoring or on manipulating keys and values.

An IXBTreeCursor works with a single IXBTree, but several IXBTreeCursors may access the same IXBTree and be positioned independently without conflict.  See the IXBTree class specification for more information on concurrent access with multiple IXBTreeCursors.

Using Hints to Speed Key Search

In addition to the basic cursoring methods described in the IXCursorPositioning protocol specification, IXBTreeCursor supports hinting.  Hints essentially allow the IXBTreeCursor to find keys by absolute position.  This can speed key search dramatically as long as the IXBTree is relatively static.  If a lot of insertions and removals are performed, however, the use of hints will probably slow down key search; hints will frequently fail to identify the physical locations of their keys because those keys will have moved, and key search will incur the cost of hint failure in addition to the cost of searching.

Instance Variables

struct BTree *btree;

void *keyBuffer;

unsigned int bufferSize;

unsigned int keyLength;

unsigned int keyLimit;

unsigned int traceHint;

unsigned int cursorVersion;

unsigned int cursorDepth;

NXZone *cursorZone;

struct BTreeTraceRecord *cursorTrace;

struct {...} cursorStatus;

btree	The IXBTree accessed by the IXBTreeCursor.

keyBuffer	The internal key buffer.

bufferSize	The size in bytes of the internal key buffer.

keyLength	The length of the key in the internal key buffer.

keyLimit	The maximum length in bytes of a key.

traceHint	The current hint value.

cursorVersion	Used to synchronize the activity of multiple cursors.

cursorDepth	The number of levels in the tree.

cursorZone	The memory allocation zone in which the cursor resides.

cursorTrace	The cache of the trace path followed by last key search.

cursorStatus	For internal use by the IXBTreeCursor.

Adopted Protocols

IXCursorPositioning	- setFirst
- setLast
- setNext
- setPrevious
- setKey:andLength:
- getKey:andLength:
- isMatch

Method Types

Initializing an IXBTreeCursor	- initWithBTree:

Accessing the IXBTree	- btree

Positioning with hints	- setKey:andLength:withHint:
- getKey:andLength:withHint:

Accessing IXBTree data	- writeValue:andLength:
- writeRange:ofLength:atOffset:
- readValue:
- readRange:ofLength:atOffset:
- removeValue

Instance Methods

btree

- (IXBTree *)btree

Returns the IXBTree that the IXBTreeCursor accesses.  This is useful if your code didn't initialize the IXBTreeCursor, since it allows your code to reconfigure the IXBTree, or empty or free it.

See also:  - initWithBTree:

getKey:andLength:withHint:

- (BOOL)getKey:(void **)aKey
andLength:(unsigned int *)aLength
withHint:(unsigned int *)aHint

Returns by reference the key defining the IXBTreeCursor's position in its IXBTree, along with the key's length, and a hint that your code can use to speed up a subsequent key search for the same key using setKey:andLength:withHint:.  The hint is guaranteed to remain useful as long as no insertions or removals are performed; however, the more the IXBTree changes, the less useful the hint becomes.

Note:  Your application should use the NXSwapBigTypeToHost() function to convert the byte-order of the retrieved key to that of the machine it's running on.

If the IXBTreeCursor is at a key, this method returns YES.  If the IXBTreeCursor is between two keys or before the first one, this method advances it to the next key and returns YES.  If the IXBTreeCursor is beyond the last key, this method returns NO, and the contents of aKey, aLength, and aHint are undefined.

The contents of aKey aren't guaranteed to remain valid across subsequent messages to the IXBTreeCursor, since it may relocate its key buffer.  Your code should copy its contents if it needs to save them.  Your code should not write into the buffer pointed to by aKey; doing so may corrupt your application's memory, causing errors or a crash.

See also:  - getKey:andLength: (IXCursorPositioning protocol), - setKey:andLength:withHint:

initWithBTree:

- initWithBTree:(IXBTree *)aBTree

Initializes the IXBTreeCursor to work with aBTree.  It will use that IXBTree's comparator or comparison format to position itself at keys.  This is the designated initializer for IXBTreeCursors.  Returns self.

See also:  - btree

readRange:ofLength:atOffset:

- (unsigned int)readRange:(void **)aRange
ofLength:(unsigned int)aLength
atOffset:(unsigned int)anOffset

Copies a portion of the value in the IXBTree at the IXBTreeCursor's position, and returns the length actually read (which may be less than the length requested).  If there is no key/value pair at the IXBTreeCursor's position, the IX_NotFoundError exception is raised.

Note:  Your application should use the NXSwapBigTypeToHost() function to convert the byte-order of retrieved data to that of the machine it's running on.

If *aRange is NULL, then up to aLength bytes will be allocated from the IXBTreeCursor's zone, and the data will be copied into that buffer.  Your code is responsible for freeing the memory allocated.  If a non-NULL value is provided in *aRange, then it is assumed to be the address of a valid buffer, and up to aLength bytes will be copied into it starting from anOffset within the IXBTree's value.

Important:  Using the address of an uninitialized pointer variable as aRange is incorrect, and will result in data being copied into a random location in the application's address space.  Your code should always allocate memory for the pointer variable or set it to NULL before passing its address to this method.

See also:  - readValue:, - writeValue:andLength:, - writeRange:ofLength:atOffset:, - openRange:ofLength:atOffset:forWriting:,  - removeValue

readValue:

- (unsigned int)readValue:(void **)aValue

Copies the value in the IXBTree at the IXBTreeCursor's position, and returns the length of the value.  If there is no key/value pair at the IXBTreeCursor's position, the IXBTreeCursor moves to the next higher position if possible.  If the IXBTreeCursor is at the end of the key space, IX_NotFoundError is raised.

Note:  Your application should use the NXSwapBigTypeToHost() function to convert the byte-order of retrieved data to that of the machine it's running on.

If *aValue is NULL, then a buffer will be allocated from the IXBTreeCursor's zone, and the data will be copied into that buffer.  Your code is responsible for freeing the memory allocated.  If a non-NULL value is provided in *aValue, then it is assumed to be the address of a valid buffer, and the value stored in the IXBTree will be copied into it.  Your code is responsible for making sure the buffer is large enough to hold the value.  This is useful for fixed-length values, or values with a known maximum length.

Important:  Using the address of an uninitialized pointer variable as aValue is incorrect, and will result in data being copied into a random location in the application's address space.  Your code should always allocate memory for the pointer variable or set it to NULL before passing its address to this method.

This method may be used to determine the size of the buffer needed: invoke it first with NULL as aValue to get the buffer length without copying the data, then a second time with the length to copy the data.  This is an efficient usage pattern, unless multiple cursors are active, in which case, it will be very inefficient if the tree is modified by another cursor between the two invocations.

See also:  - writeValue:, - removeValue, - readRange:ofLength:atOffset:, - writeRange:ofLength:atOffset:

removeValue

- removeValue

Removes the key and the associated value at the IXBTreeCursor's position.  This method raises IX_NotFoundError if there is no key at the IXBTreeCursor's position.  Returns self.

See also:  - readValue:, - writeValue:, - readRange:ofLength:atOffset:, - writeRange:ofLength:atOffset:

setKey:andLength:withHint:

- (BOOL)setKey:(void *)aKey
andLength:(unsigned int)aLength
withHint:(unsigned int)aHint

Positions the IXBTreeCursor at aKey if aKey is stored in the IXBTree; otherwise, positions the IXBTreeCursor where aKey would be (which may be between two keys, or off either end of the key space).  aLength is the length of aKey.  Returns YES if aKey is in the IXBTree (that is, if the IXBTreeCursor finds the key), and NO if it's not.

Note:  Your application should use the NXSwapHostTypeToBig() function before invoking this method, to convert the byte-order of the key to big-endian (the standard byte-order for the Indexing Kit).

This method uses a hint as returned by getKey:andLength:withHint: to find aKey quickly.  A hint is like a bookmark; it defines a physical position in the IXBTree, so the IXBTreeCursor can just go there and check if aKey is still there.  If the IXBTree has been modified, aKey may no longer reside at the position indicated by aHint; in that case a key search is performed.  Using hints can actually slow down key search in highly dynamic IXBTrees; use them for reading static or read-only IXBTrees.

See also:  - getKey:andLength:withHint:, - getKey:andLength: (IXCursorPositioning protocol), - setKey:andLength: (IXCursorPositioning protocol)

writeRange:ofLength:atOffset:

- writeRange:(void *)aRange
ofLength:(unsigned int)aLength
atOffset:(unsigned int)anOffset

Writes aRange over a portion of the value in the IXBTree at the IXBTreeCursor's position.  Data starting at anOffset within the IXBTree's value is overwritten for aLength bytes.  If the range would extend past the end of the value, the value is enlarged to hold the new amount.  Returns self.

Note:  Your application should use the NXSwapHostTypeToBig() function before invoking this method, to convert the byte-order of the data to big-endian (the standard byte-order for the Indexing Kit).

If there is no key/value pair at the IXBTreeCursor's position, this method raises IX_NotFoundError.

See also:  - readRange:ofLength:atOffset:, - readValue:, - writeValue:andLength:, - removeValue

writeValue:andLength:

- (BOOL)writeValue:(void *)aValue andLength:(unsigned int)aLength

Writes aLength bytes from aValue as the value in the IXBTree at the IXBTreeCursor's position, possibly overwriting a previously stored value.  Returns YES if the write resulted in an insertion, and NO if the write overwrote a previously stored value.

Note:  Your application should use the NXSwapHostTypeToBig() function before invoking this method, to convert the byte-order of the data to big-endian (the standard byte-order for the Indexing Kit).

Overwriting completely replaces a value; the previous value is removed and replaced with a new one.  If the IXBTreeCursor is not positioned at a key/value pair, a new pair will be inserted with the key last used to position the IXBTreeCursor (with setKey:andLength: or setKey:andLength:withHint:).  For example, inserting a completely new value into the IXBTree involves positioning the IXBTreeCursor, checking that the positioning method returns NO (that is, that it didn't find an existing value), and simply using writeValue:andLength: to insert the new value with the key just set.

See also:  - readValue:, - removeValue, - readRange:ofLength:atOffset:, - writeRange:ofLength:atOffset: